路径规划算法中，有一类算法是概率完备的，其中的经典算法包括PRM以及今天的主角——RRT。本文将简要介绍RRT以及它的两个变体——RRT*和RRT*-Smart。

RRT的中文名的快速随机探索树，它的原理很简单，实际上就是维护一棵路径树：从起点开始，在空间中随机采样，并找到路径树上与采样点最接近且能与它无障碍地连接的点，连接这个点与采样点，将采样点加入路径树，直至终点附近区域被探索到。这种方式无法保证得到的路径是最优的。

RRT*在RRT基础上做了改进，主要是进行了重新选择父节点和重布线的操作。试想在RRT中，我们的采样点最终与整棵树上和它最近的点连了起来，但这未必是最好的选择，我们的最终目的是让这个点与起点的距离尽可能近。RRT*便对此做了改进，它在采样点加入路径树以后，以其为圆心画了一个小圈，考虑是否有更好的父节点，连到那些节点上能使起点到该点的距离更短（尽管那些节点并不是离采样点最近的点）。如果选择了更加合适的父节点，那么就把它们连接起来，并去除原来的连线（重布线）。

RRT*-Smart在RRT*的基础上做了改进，主要是优化了路径。通过RRT和RRT*探索出的路径往往是曲曲折折有些小波浪的（毕竟节点是随机生成的），但事实上上在空地中的最佳路径一般是直线。RRT*-Smart在运行的前一个阶段与RRT*完全一致，但是找到一条可行的从起点到终点的路径之后它就开始考虑优化路径，化曲为直。这个过程实际上就是从叶子节点开始，不断寻找能否无障碍地直接连接到先辈节点。如果直接往前连一层就多一条直线，少一段曲线。（为了增加运算速度，不妨直接把障碍物都视为矩形的）在化曲为止的过程中，我们能找到几个锚点，这些点往往是在障碍物附近的，它们无法帮助子孙们直接优化。

在之后的循环中，我们加入Smart采样的方式，而不全是随机采样，也就是在这些锚点附近增加采样，从而更有可能找到最优的路径。RRT*-Smart的规划效果下图(b)[1]。

基于RRT，针对不同的场景有十多个变种，有些是彻底的改进，有些则是适配特殊的环境。如果想了解更多，可以参考wiki上的RRT页面[2]。